\select@language {spanish}
\contentsline {section}{\numberline {1}Enunciado e Introducci'on}{4}
\contentsline {subsection}{\numberline {1.1}Extracto del enunciado}{4}
\contentsline {subsection}{\numberline {1.2}Introduccion Te'orica}{4}
\contentsline {subsection}{\numberline {1.3}Objetivo}{4}
\contentsline {subsection}{\numberline {1.4}Consideraciones generales}{4}
\contentsline {section}{\numberline {2}Ejemplo de la vida real:}{5}
\contentsline {subsection}{\numberline {2.1}Juan Carlos cambia el mundo, MAX-POLITIC-SAT}{5}
\contentsline {subsection}{\numberline {2.2}Juan ``Tribunero'' Carlos y el equipo de la gente, MAX-FUTBOL-SAT}{5}
\contentsline {section}{\numberline {3}Algoritmo Exacto}{6}
\contentsline {subsection}{\numberline {3.1}Introducci'on}{6}
\contentsline {subsection}{\numberline {3.2}Soluci'on}{6}
\contentsline {subsection}{\numberline {3.3}Pseudoc'odigo}{6}
\contentsline {subsubsection}{\numberline {3.3.1}Explicaci'on}{6}
\contentsline {subsection}{\numberline {3.4}An'alisis de Complejidad}{7}
\contentsline {subsection}{\numberline {3.5}Experimentos y Gr'aficos}{7}
\contentsline {subsubsection}{\numberline {3.5.1}De los casos de prueba}{7}
\contentsline {subsubsection}{\numberline {3.5.2}Gr'aficos complejidad te'orica vs Complejidad medida en la pr'actica}{8}
\contentsline {subsection}{\numberline {3.6}Conclusiones}{12}
\contentsline {subsubsection}{\numberline {3.6.1}En cuanto a la complejidad del algoritmo}{12}
\contentsline {subsubsection}{\numberline {3.6.2}En cuanto a la soluci'on propuesta}{12}
\contentsline {section}{\numberline {4}Heur'istica Constructiva}{13}
\contentsline {subsection}{\numberline {4.1}Introducci'on}{13}
\contentsline {subsection}{\numberline {4.2}Soluci'on}{13}
\contentsline {subsection}{\numberline {4.3}Pseudoc'odigo}{14}
\contentsline {subsubsection}{\numberline {4.3.1}Explicaci'on}{14}
\contentsline {subsubsection}{\numberline {4.3.2}Observaciones:}{14}
\contentsline {subsubsection}{\numberline {4.3.3}constructivaGolosa}{14}
\contentsline {subsubsection}{\numberline {4.3.4}removerClausulas}{15}
\contentsline {subsubsection}{\numberline {4.3.5}buscarVariableQUeMasAparecio}{15}
\contentsline {subsubsection}{\numberline {4.3.6}contarApariciones}{15}
\contentsline {subsubsection}{\numberline {4.3.7}buscarClausulasResueltas}{15}
\contentsline {subsection}{\numberline {4.4}An'alisis de Complejidad}{16}
\contentsline {subsubsection}{\numberline {4.4.1}funci'on contarApariciones}{16}
\contentsline {subsubsection}{\numberline {4.4.2}funci'on removerClausulas}{16}
\contentsline {subsubsection}{\numberline {4.4.3}funci'on buscarVariableQueMasAparecio}{16}
\contentsline {subsubsection}{\numberline {4.4.4}funci'on buscarClausulasResultas}{16}
\contentsline {subsubsection}{\numberline {4.4.5}funci'on constructivaGolosa}{17}
\contentsline {subsection}{\numberline {4.5}Experimentos y Gr'aficos}{18}
\contentsline {subsubsection}{\numberline {4.5.1}De los casos de prueba}{18}
\contentsline {subsubsection}{\numberline {4.5.2}Gr'aficos complejidad te'orica vs Complejidad medida en la pr'actica}{19}
\contentsline {subsubsection}{\numberline {4.5.3}Comparaci'on de resultados Algoritmo Exacto vs Heur'istica Constructiva}{25}
\contentsline {subsection}{\numberline {4.6}Conclusiones}{26}
\contentsline {section}{\numberline {5}Heur'istica de B'usqueda Local}{27}
\contentsline {subsection}{\numberline {5.1}Introducci'on}{27}
\contentsline {subsection}{\numberline {5.2}Soluci'on}{28}
\contentsline {subsection}{\numberline {5.3}Pseudoc'odigo}{29}
\contentsline {subsubsection}{\numberline {5.3.1}Explicaci'on}{29}
\contentsline {subsection}{\numberline {5.4}An'alisis de Complejidad}{29}
\contentsline {subsubsection}{\numberline {5.4.1}Demostraci'on}{30}
\contentsline {subsection}{\numberline {5.5}Experimentos y Gr'aficos}{31}
\contentsline {subsubsection}{\numberline {5.5.1}Resultados obtenidos}{31}
\contentsline {subsubsection}{\numberline {5.5.2}Complejidad}{35}
\contentsline {subsection}{\numberline {5.6}Conclusiones}{36}
\contentsline {section}{\numberline {6}Heur'istica de Tab'u Search}{37}
\contentsline {subsection}{\numberline {6.1}Introducci'on}{37}
\contentsline {subsection}{\numberline {6.2}Soluci'on}{37}
\contentsline {subsection}{\numberline {6.3}Pseudoc'odigo}{38}
\contentsline {subsubsection}{\numberline {6.3.1}Explicaci'on}{38}
\contentsline {subsubsection}{\numberline {6.3.2}Acerca de las inicializaciones, estructuras y m'etodos}{38}
\contentsline {subsubsection}{\numberline {6.3.3}Explicaci'on de la heur'istica}{39}
\contentsline {subsubsection}{\numberline {6.3.4}\textquestiondown Por qu'e guardamos movimientos en la lista tab'u?}{39}
\contentsline {subsection}{\numberline {6.4}An'alisis de Complejidad}{39}
\contentsline {subsubsection}{\numberline {6.4.1}An'alisis de los for anidados}{40}
\contentsline {subsubsection}{\numberline {6.4.2}An'alisis del while}{40}
\contentsline {subsubsection}{\numberline {6.4.3}Complejidad total}{40}
\contentsline {subsection}{\numberline {6.5}Experimentos y Gr'aficos}{40}
\contentsline {subsubsection}{\numberline {6.5.1}Experimentos para determinar complejidad emp'iricamente}{40}
\contentsline {subsubsection}{\numberline {6.5.2}Experimentos para comparar los resultados entre los algoritmos}{47}
\contentsline {subsubsection}{\numberline {6.5.3}Experimentos para determinar criterios de parada}{49}
\contentsline {subsection}{\numberline {6.6}Conclusiones}{52}
\contentsline {subsubsection}{\numberline {6.6.1}Acerca de las mejoras del algoritmo}{52}
\contentsline {subsubsection}{\numberline {6.6.2}Acerca de las decisiones}{52}
\contentsline {subsubsection}{\numberline {6.6.3}Acerca de la complejidad}{52}
\contentsline {subsubsection}{\numberline {6.6.4}Acerca de los resultados y comparaciones}{52}
